1. Field of the Invention
The present invention generally relates to a long-thin wireless network, and in particular, to a network address assigning and allocating method and a routing method for a long-thin wireless network.
2. Description of Related Art
In recent years, many wireless network applications, such as tour guide service, positioning service, and environment monitoring, have been developed along with the rapid advancement of wireless network technology. In these applications, the nodes in a wireless network are connected in a multi-hop pattern, and when a particular data source node is about to transmit data to a target node, the data has to be relayed by some intermediate nodes. Most environment monitoring applications adopt such a network transmission pattern. However, in a multi-hop network, different type of network topology should be adopted according to different application. For example, the network could be a star network, a tree network, a long-thin network, or an ultra-long-thin network, etc.
FIG. 1 is a diagram of a conventional ultra-long-thin network. Referring to FIG. 1, most nodes in the network are connected in a long-thin pattern, and the other nodes are connected to those long-thin nodes to serve as communication bridges in between. Such a network topology is adopted by many environment monitoring applications, such as highway lamp monitoring, tunnel monitoring, oil pipeline monitoring, and gas pipeline monitoring, etc.
It is a difficult work to assign network addresses to nodes in such an ultra-long-thin network. The allocation of network addresses is generally categorized into manual allocation and automatic allocation. It is very timing-consuming to manually allocate network addresses in such an ultra-long-thin network, while most existing automatic network address allocating methods designed especially for wireless networks require very complicated calculations and cannot guarantee that a unique network address is assigned to each of the network nodes.
Recently, a low-complexity address assigning algorithm is provided by the ZigBee alliance. According to this algorithm, an address calculation method similar to a geometric proportion expression is adopted for assigning addresses, and each network node has to be assigned with a 16-bit network address, otherwise the network node will not be considered as a network member. A distributed network address assigning algorithm is designed by the ZigBee alliance, in which the nodes in a network compete to become a ZigBee coordinator when the network is just started. Assuming that a specific device successfully becomes the ZigBee coordinator, the ZigBee coordinator scans all the wireless channels and determines a suitable operation channel. After that, the ZigBee coordinator broadcasts a beacon frame to allow other devices to join its network. When another device receives the beacon frame, it executes a process to join the network and accordingly becomes a ZigBee router or a ZigBee end device.
If a specific device becomes a ZigBee router, the ZigBee router also broadcasts a beacon frame to allow other devices which have not joined the network to join the network. Whenever a device successfully joins the network, the transmitter of the beacon frame allocates a network address to the device as an identification (ID) for transmitting data subsequently. The ZigBee coordinator first defines the maximum number of devices to be connected to a ZigBee router (Cm), the maximum number of ZigBee sub-routers (Rm), and the depth of the network (Lm). It is specified by ZigBee alliance that Cm≧Rm. Accordingly, at least (Cm-Rm) ZigBee end devices can be connected to a ZigBee router.
According to the ZigBee specification, the network address of a device is allocated by a parent node thereof. As to a ZigBee coordinator, the address space of the entire network is divided into Rm+1 blocks, in which the address space of the first Rm blocks is assigned to Rm sub-routers thereof, and the remaining portion is kept for (Cm-Rm) ZigBee end devices connected thereto. In the present algorithm, a ZigBee router calculates a parameter Cskip using Cm, Rm, and Lm and then calculates and assigns network addresses to its sub-routers and end-devices by using the parameter Cskip. Assuming that the ZigBee router is located at the dth level of the network, then the value of the parameter Cskip can be calculated through:
      Cskip    ⁡          (      d      )        =      {                                                      1              +                              C                ⁢                                                                  ⁢                                  m                  ·                                      (                                          Lm                      -                      d                      -                      1                                        )                                                                        ,                                                              if              ⁢                                                          ⁢              Rm                        =            1                                                                                          1                +                                  C                  ⁢                                                                          ⁢                  m                                -                Rm                -                                  C                  ⁢                                                                          ⁢                                      m                    ·                                          Rm                                              Lm                        -                        d                        -                        1                                                                                                                        1                -                Rm                                      ,                                                Otherwise            .                              
According to the ZigBee specification, a ZigBee coordinator is located at depth 0 of a network. Assuming a router x is located at depth d and a node y is a child of the router x, then Cskip(d) represents the maximum number of nodes (including the node y) in a subtree having the node y as its root. On the other hand, the assigning of network addresses is started from the ZigBee coordinator, in which the ZigBee coordinator assigns 0 as its own address and depth. Assuming that the address of a parent node located at depth d is Aparent, the parent node then assigns Aparent+(n−1)×Cskip(d)+1 as the address of its nth sub-router and Aparent+Rm×Cskip(d)+n as the address of its nth end device.
However, in foregoing ZigBee algorithm, the maximum number of child nodes of each node and the depth of the entire network are limited. Taking the ultra-long-thin network topology 200 illustrated in FIG. 2 as an example, at most two sub-routers can be connected to a node, namely, Cm=Rm=2. If the ZigBee address assigning method described above is adopted for assigning network addresses (i.e. using 16-bit network addresses), network addresses can be assigned to at most 15 levels of the network. Thus, the ZigBee address assigning method is not suitable for ultra-long-thin network which usually has a network depth greater than 15.